package sort;


public class Sortierverfahren
{
    public static void bubbleSort(int[] list)
    {
        bubbleSort(list, 0, list.length - 1);
    }

    public static void bubbleSort(int[] list, int leftIdx, int rightIdx)
    {
        if (leftIdx < 0 || rightIdx < 0 || leftIdx > list.length || rightIdx > list.length)
        {
            throw new IllegalArgumentException("Fehler");
        }
        else
        {
            boolean unsortiert = true;
            do
            {
                unsortiert = false;

                for (int i = leftIdx; i < rightIdx; i++)
                {
                    if (list[i] > list[i + 1])
                    {
                        // Elemente vertauschen
                        swap(list, i, i + 1);
                        unsortiert = true;
                    }
                }
                rightIdx--;
                // solange Vertauschung auftritt
            }
            while (unsortiert);
        }
    }

    public static void bubbleUp(int[] list, int leftIdx, int i)
    {
        if (leftIdx < 0 || i < 0 || leftIdx > list.length || i > list.length)
        {
            throw new IllegalArgumentException("Fehler");
        }
        else
        {
            for (int k = leftIdx; k < i - 1; k++)
            {
                if (list[k] > list[k + 1])
                {
                    swap(list, k, k + 1);
                }
            }
        }
    }

    public static void quickSort(int[] list)
    {
        quickSort(list, 0, list.length - 1);
    }

    public static void quickSort(int[] list, int leftIdx, int rightIdx)
    {
        if (leftIdx < 0 || rightIdx < 0 || leftIdx > list.length || rightIdx > list.length)
        {
            throw new IllegalArgumentException("Fehler");
        }
        else
        {
            int l = leftIdx;
            int r = rightIdx;
            int key = list[(rightIdx + leftIdx) / 2];
            while (l <= r)
            {
                while (key < list[r])
                {
                    r--;
                }
                while (list[l] < key)
                {
                    l++;
                }
                if (l <= r)
                {
                    swap(list, l, r);
                    r--;
                    l++;
                }
            }
            if (leftIdx < r)
            {
                quickSort(list, leftIdx, r);
            }
            if (l < rightIdx)
            {
                quickSort(list, l, rightIdx);
            }
        }
    }

    public static int divide(int[] list, int leftIdx, int rightIdx)
    {
        if (leftIdx < 0 || rightIdx < 0 || leftIdx > list.length || rightIdx > list.length)
        {
            throw new IllegalArgumentException("Fehler");
        }
        else
        {
            int l = leftIdx, r = rightIdx - 1;
            int pivot = list[rightIdx];
            while (l <= r)
            {
                while (pivot < list[r])
                {
                    r--;
                }
                while (list[l] < pivot)
                {
                    l++;
                }
                if (l <= r)
                {
                    if (l < r)
                    {
                        swap(list, l, r);
                    }
                    r--;
                    l++;
                }
            }
            return pivot;
        }
    }

    public static void swap(int[] list, int i, int j)
    {
        if (i < 0 || j < 0 || i > list.length || j > list.length)
        {
            throw new IllegalArgumentException("Fehler!");
        }
        else
        {
            list[i] ^= list[j];
            list[j] ^= list[i];
            list[i] ^= list[j];
        }
    }

    public static String toString(int[] list, int start, int end)
    {
        String listString = "";
        if (start < 0 || end < 0 || start > list.length || end > list.length)
        {
            throw new IllegalArgumentException("Fehler");
        }
        else
        {
            for (int i = start; i <= end; i++)
            {
                listString = listString + String.valueOf(list[i]) + "\n";
            }
            return listString;
        }
    }

    public static String toString(int[] list)
    {
        return toString(list, 0, list.length - 1);
    }

    public static void main(String[] args)
    {
        int[] list1 = new int[1000000];
        for (int i = 0; i < list1.length; i++)
        {
            list1[i] = (int) Math.random();
        }

        long zeit1 = System.currentTimeMillis();
        bubbleSort(list1);
        long zeit2 = System.currentTimeMillis();
        System.out.println((zeit2 - zeit1));

        int[] list2 = new int[1000000];
        for (int i = 0; i < list2.length; i++)
        {
            list2[i] = (int) Math.random();
        }

        long zeit3 = System.currentTimeMillis();
        quickSort(list2);
        long zeit4 = System.currentTimeMillis();
        System.out.println((zeit4 - zeit3));

    }
}
